//
//  LeetCode455.hpp
//  DataStructuresAndAlgorithms
//
//  Created by blue on 2020/7/21.
//  Copyright © 2020 blue. All rights reserved.
//
/*
 例1：分糖果
 已知一些孩子和一些糖果，每个孩子有需求因子g，么个糖果有大小s，当某个糖果的大小s >= 某个孩子的需求因子g时，代表改糖果可以满足该孩子；求使用这些糖果最大能满足多少孩子？（注意，某个孩子最多只能用1个糖果满足）
 
 例如，需求因子数组 g = [5,10,2,9,15,9];糖果大小数组 s = [6,1,20,3,8];最多可以满足3个孩子。
 
 选自：LeetCode 455 Assign Cookies
 难度：Easy
 
 */
#ifndef LeetCode455_hpp
#define LeetCode455_hpp

#include <stdio.h>
#include <vector>

/*
 例1：思考
 例如，需求因子数组 g = [5,10,2,9,15,9]; 糖果大小数组 s = [6,1,20,3,8]。
 为了更明显的判断某个孩子可以被某个糖果满足，对g，s排序后观察：
 g = [2,5,9,9,10,15];   s = [1,3,6,8,20]
 
 1. 当某个孩子可以被多个糖果满足时，是否需要优先用某个糖果满足这个孩子？
 2. 当某个糖果可以满足多个孩子时，是否需要优先满足某个孩子？
 
 
 
 
 
 例1：贪心规律
 需求因子数组 g = [5,10,2,9,15,9]; 糖果大小数组 s = [6,1,20,3,8]。
 核心目标：让更多孩子得到满足，有如下规律：
 
 1.某个糖果如果不能满足某个孩子，则该糖果也一定不能满足需求因子更大的孩子。
 如，
 糖果1（s = 1）不能满足孩子1（g = 2），则不能满足孩子2、孩子3、...、孩子7；
 糖果2（s = 3）不能满足孩子2（g = 5），则不能满足孩子3、孩子4、...、孩子7；
 
 2.某个孩子可以用更小的糖果满足，则没必要用更大糖果满足，因为可以保留更大的糖果满足需求因子更大的孩子。（贪心！）
 如，
 孩子1（g = 2），可以被糖果2（s = 3）满足，则没必要用糖果3、糖果4、糖果5满足；
 孩子2（g = 5），可以被糖果3（s = 6）满足，则没必要用糖果4、糖果5满足；
 
 3.孩子的需求组因子更小则其更容易被满足，故优先从需求因子小的孩子尝试，可以得到正确的结果。
 
 
 
 
 
 
 例1：算法思路
 1. 对需求因子数组g 与糖果大小数组s 进行从小到大的排序。
 2. 按照从小到大的顺序使用各糖果尝试是否可满足某个孩子，每个糖果只尝试1次；若尝试成功， 则换下一个孩子尝试；知道发现没更多的孩子或者没更多的糖果，循环结束。
 */
class Solution455 {
public:
    //返回最多可以有多少孩子被满足
    int findContentChildren(std::vector<int> &g, std::vector<int> &s);
};

#endif /* LeetCode455_hpp */
